package com.hyb.algorithm.data.struct.dp;

/**
 * @Author: huyanbing
 * @Date: 2021/9/1 7:43 下午
 * <p>
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/
 * <p>
 * 123. 买卖股票的最佳时机 III
 * <p>
 * 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
 * <p>
 * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
 * <p>
 * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class MaxProfit3 {

    public static void main(String[] args) {

        MaxProfit3 exe = new MaxProfit3();

        //int[] arr = new int[]{2, 1, 2, 0, 1};
        //int[] arr = new int[]{3, 3, 5, 0, 0, 3, 1, 4};
        int[] arr = new int[]{1, 2, 3, 4, 5};
        int ret = exe.maxProfit(arr);

        System.out.println(ret);
    }

    public int maxProfit(int[] prices) {
        int n = prices.length;

        if (n <= 0) {
            return 0;
        }

        int max = 2;
        int[][][] dp = new int[n][max + 1][2];

        dp[0][2][0] = 0;
        dp[0][2][1] = Integer.MIN_VALUE;

        dp[0][1][0] = 0;
        dp[0][1][1] = -prices[0];

        int i = 0;

//        dp[i][2][0] = Math.max(0, Integer.MIN_VALUE + prices[i]);
//        dp[i][2][1] = Math.max(Integer.MIN_VALUE, Integer.MIN_VALUE - prices[i]);
//        dp[i][1][0] = Math.max(0, Integer.MIN_VALUE + prices[i]);
//        dp[i][1][1] = Math.max(Integer.MIN_VALUE, -prices[i]);


        for (i = 1; i < n; i++) {
            for (int k = max; k >= 1; k--) {
                dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
                dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]);
            }
        }


        return Math.max(dp[n - 1][max][0], dp[n - 1][max - 1][0]);
    }
}
